Eagles Nest BBS 5

home *** CD-ROM | disk | FTP | other *** search

/ Eagles Nest BBS 5 / Eagles_Nest_Mac_Collection_Disc_5.TOAST / Other Non-Macintosh Text / CountTheorem / count.TXT

Wrap

Text File | 1994-04-13 | 48KB | 940 lines

A RECONSIDERATION OF THE DIAGONALIZATION THEOREM by R. Webster Kehr Sprint Corporation (c) Copyright March 24, 1994 by R. Webster Kehr, All Rights Reserved. This paper *may* be freely photocopied and/or electronically transmitted if and only if it is photocopied/transmitted in its entirety. No fee or royalty is requested. However, no part of this paper may be published in a magazine or other periodical without written permission of the copyright owner. This paper may be retyped as long as this copyright notice is included. ASCII notations used in this paper: N/o Aleph Naught or Aleph Null, the cardinality of the counting or natural numbers. [n] The set of all counting number from 1 to n, meaning {1, 2, 3, 4, ..., n-1, n}. Set R+ The set of all terminating decimals in R. Set Rnt The set of all non-terminating decimals in R, meaning all non-terminating rational numbers, all algebraic irrational numbers and all transcendental irrational numbers. Other notations will be defined as they are introduced. In 1873 Georg Cantor published the first proof that the real numbers were uncountable. Since then there have been many other proofs of this concept. Cantor himself came out with his famous Diagonalization Theorem in 1891, upon which the theorems of many other mathematicians have re- lied. Other proofs of R's uncountability have also been developed using a variety of different approaches. This paper will deal mainly with the Diagonalization Theorem, but will discuss more general approaches as well. In this paper two major theorems about the counting numbers (a.k.a. positive integers, natural numbers, positive whole real numbers, etc.), defined as Set A, will be proven. These theorems are vital to understand in any discussion of the Diagonalization Theorem. SECTION 1) TWO THEOREMS ABOUT THE NATURE OF THE COUNTING NUMBERS Introduction to Theorem #1: In this paper the term "countable" means "infinite and countable." Sometimes the latter phrase will be used to add emphasis. DEFINITIONS: The "width" of a number and the "width" of a set. The "width" of a single number is a subset of the counting numbers (not necessarily proper), always beginning with the number 1, which maps to the significant digits in that number. For example, the number: 753.056109 has 9 significant digits in it. The "width" or "width set" of this number is therefore: {1, 2, 3, 4, 5, 6, 7, 8, 9} or [9]. In es- sence, the counting numbers are being mapped to the significant digit po- sitions, or indexed significant digit positions of the number. The "width" can be thought of as a set of indexes, but they are technically a *set* of counting numbers, nevertheless. As another example, the width of pi is {1, 2, 3, 4, ...}, the set of all counting numbers. The "width" of a *set* (i.e. the original set is called the "parent" set) is a subset of counting numbers (not necessarily proper), beginning with the number 1, which maps to the significant digit positions of the element of the set with the maximum width. In other words, it is the set of counting numbers from 1 to the supremum of the set of cardinalities of the widths of the elements of the set. If the supremum is n, the width set is [n]. For example, consider the following set (the second column repre- sents the cardinality of the width of that element): 1,543,123.30000000000000... 8 789,321.40000000000000... 7 109.00000000000300... 15 42,109.32000000000000... 7 The cardinality of the above set is 4 (i.e. it has 4 elements), but the cardinality of the width (set) of the above set is 15 (i.e. the supremum of the set of cardinalities of widths). The width of the above set is therefore [15]. The cardinality of a parent set may be less than, equal to, or greater than the cardinality of its width (set). For infinite sets of numbers the width of the set is the set of *all* counting numbers (this will be proven below). This would make the cardinality of the width of the set countable, meaning the cardinality of the width set is N/o, and the width itself is [N/o]. It is important to understand that in this paper theorems regarding cardinality are based on two different types of sets. The cardinality of a set is the number of elements in the set. The cardinality of the width of a set is the cardinality of the subset of counting numbers which make up the width of the set. If the meaning is clear from the context, the term "width" of a set will also be used to mean "the cardinality of the width of a set." This is reasonable because calculating the width set of a set and calculating the cardinality of the width set of a set are re- ally the same thing. The term "width" of a set implies the "cardinality of the width set." Applying standard cardinality rules to (the cardinality of) width sets yields vital information about the cardinality of parent sets, espe- cially when dealing with infinite sets, as will soon be seen. A Note On Permutations: Before proceeding a note needs to be made about the representation of the terminating decimals. Let Set R+ be the set of all terminating decimals in R. Let Set R+ (0,1) be the set of all terminating decimals in R (0,1). For any finite width, n, Set R+ (0,1) contains all permuta- tions of n digits drawn from the set of characters {0, 1, 2, ..., 9}. In other words, take any width, n; for the subset of Set R+ (0,1) of all el- ements with a width of n or less (since terminating zeros are not significant, elements with less than a width of n need to be included), the cardinality of this subset will be 10 ^ n. For example, consider the cardinality of the subset of Set R+ (0,1) with less than or equal to 1,000,000 digits. This subset of Set R+ (0,1) would contain all permutations of 1,000,000 digits drawn from the set {0, 1, 2, ... , 9}. This set would have a cardinality of 10 ^ 1,000,000 and would include all elements of Set R+ (0,1) with less than or equal to 1,000,000 digits. If terminating zeros *to width n only* were significant, the cardin- ality of Set R+ (0,1), for elements which had *exactly* a width of n, would also be 10 ^ 1,000,000. In other words, the cardinality of Set R+ to a width of n is equal when considering two different cases; case 1: if terminating zeros are not significant, then elements of the set with less than a width of n need to be included, and case 2: if terminating zeros, to width n, are significant, then *all* elements of the set with less than a width of n need to be excluded. It should be obvious why these two representations have the same cardinality. It is important to remem- ber that both cases have equal cardinality. Permutations and Binary Trees: For a moment, let's think about binary trees. The non-terminating decimals, in base 2 of course, between 0 and 1, can be thought of as non-terminating "paths" on a binary tree, where the trunk position of the tree represents a decimal point and each subsequent level of branches represents a digit position of a base 2 number. Each non-terminating number is represented by a non-terminating path along the binary tree. For example, a non-terminating decimal might be represented by .1001001111001101 and so on. Each digit is mapped to a different level of branches after the trunk and the consecutive digits can be thought of as paths up the branches of the tree. Consider a binary tree for terminating decimals similarly con- structed. In this case, each branch represents a different number and a path to that number (considering terminating zeros to that branch as sig- nificant for a moment). For any digit position, n, the terminating decimals in that layer only of the binary tree represent all possible paths, terminating or non-terminating, *to that level*. The point to this discussion is that if the terminating decimals are compared to the set of non-terminating paths, to the same width, the car- dinality of both the terminating decimals and the cardinality of the non-terminating paths, to the same width or level, are identical. Returning to base 10, another question can arise, for Set R+ (0,1). Set R+ (0,1) is technically not a complete set of permutations (because terminating zeros are not significant). Suppose the terminating zeros to *every* width achieved by the nonzero digits were *significant*, would Set R+ (0,1) still be countable? Noting Cantor's proof that the rational numbers are countable, the obvious answer is yes. In Cantor's proof, no fractions were reduced into their simplest form. For example, the number: 64000000/100000000 was counted, even though its decimal expan- sion: .64000000 has only two significant digits. As another proof of this concept, consider a third binary tree for the counting numbers where the trunk represents the number 1 instead of a decimal point. For such a tree terminating zeros are significant. This obviously represents a countable tree and it is easy to map the counting numbers, for any width n, to the terminating decimals to the same width, even if terminating zeros to that width are significant for the terminat- ing decimal tree. Simply overlay the two binary trees. Note: While the proof of the theorem about to be mentioned may seem trivial to the reader, the proof should be studied anyway, the proof is here to introduce valuable concepts. Theorem #1: The width of the counting numbers and the Set R+ (0,1), *considering only significant digits*, are both aleph naught (in this case, of course, "width" refers to the set of all counting numbers) Proof: If you count the infinite nonsignificant terminating zeros behind the significant digits of each element of Set R+ (0,1), such a set obvi- ously has an infinite width. But this theorem ignores the nonsignificant terminating zeros and states that the width of both the counting numbers and Set R+ (0,1) are both infinite and countable, considering *only* sig- nificant digits. Throughout the rest of this paper *only* significant digits of the elements of Set R+ will be considered, unless otherwise noted. This means that only the number of digits from the decimal point to the last nonzero digit will be counted as far as the width of Set R+ is concerned. Let's define four sets: Let Set A be the set of all counting num- bers. Let Set A5 be the subset of Set A defined thusly: all elements of Set A which have only 5s as digits. Let Set R+ (0,1) be defined as above. Let Set R5 be the subset of Set R+ (0,1) defined thusly: all el- ements of Set R+ (0,1) which have only 5s as digits. Now consider the following double mapping - Set A ==> Set A5 ==> Set R5: Set A Set A5 Set R5 1 5 .5 2 55 .55 3 555 .555 4 5555 .5555 5 55555 .55555 6 555555 .555555 and so on. Note that at all times, the nth element of Sets A5 and R5 have a width of n. For example, the 5,000th element of Set A5 has 5,000 5s in it. Its width set would therefore be = {1, 2, 3, ..., 4999, 5000}. The 5000th element of Set R5 has a decimal followed by 5000 5s. Its width is also the first 5000 counting numbers. Now suppose we did not know the cardinality of Set A5 or Set R5. We would know this: whatever the cardinality of Set A5 is, it is equal to the cardinality of the width (set) of Set A5. For example, if the cardinality of Set A5 is 5 billion, then the cardinality of the width of Set A5 is 5 billion. Similarly for Set R5. Suppose the cardinality of Set A5 was not infinite, but was bounded by the number 555...555, where the number of 5s represented by the three dots is finite. This would mean that the counting numbers *must end be- fore* 555...5555, or else this element would be an element of Set A and therefore an element of Set A5. That 555...5555 would be finite is a contradiction, because Set A never ends. To put it another way, if 555...555 is a finite number, then obviously 555...5555 is also a finite number, and this would force the counting numbers to end before a finite number. The cardinality of Set A5 is aleph naught, therefore its width is also aleph naught, because its cardinality and (cardinality of) width are always equal. The width of Set A cannot be less than the width of Set A5, a subset, therefore the width of Set A is also aleph naught. For Set R5, suppose there is a bound to the number of digit posi- tions in Set R5, say it is bound by .555...555, where the number of 5s represented by the three dots was finite. Then clearly the terminating decimals would be finite. They must end before .555...5555. Let's say the number of digits in this number was 1 billion, for example. Then the cardinality of the terminating decimals would be less than 10 ^ 1 billion (this is the total number of permutations of 1 billion digits from a set of 10 characters, as was discussed above). This is a finite number, but it is well known that the number of terminating decimals is infinite. There is therefore a contradiction. The width of Set R+ (0,1) cannot be less than the width of one of its subsets, therefore Set R+ (0,1) has a width of aleph naught. Finally, it is necessary to prove that neither set is uncountable. We know Set A5 is not uncountable because it is a subset of the counting numbers. Likewise, the cardinality of Set R5 cannot become uncountable because it is a subset of both Set R+ and Set R+ (0,1), which are count- able. This also proves that the *widths* of Set A5 and Set R5 are not uncountable, because their cardinality and width are equal. Q.E.D. Corollary: Every infinite set of numbers has an infinite width of significant digit positions. Suppose an infinite set had a finite width, say w. 10 ^ w is the number of permutations of w digits from a set of 10 characters. If w is finite, so is 10 ^ w. The cardinality of the set cannot exceed this num- ber, but can be less, which means the cardinality of the set is finite, which is a contradiction to the assumption. Q.E.D. It may seem strange that the corollary is more general than the theorem, but it is vital that the reader understand Sets A5 and R5. Note that saying the width of Sets A5 and R5 are countable means there is no bound to the number of *significant* digits in the *set* of terminating decimals. In other words, there is no single digit position, among the set of all countable digit positions, which is not surpassed by the width of significant digits in the *set* of terminating decimals. If there was, then the set of terminating decimals would be finite, by a proof similar to the above proof. Another comment that could be made is that there is no single termi- nating decimal which is as wide as 5/9ths or pi. The decimal expansions of 5/9th and pi are each infinite sets of digits and digit positions. Their width is infinite, which is well known. The fact that there is no *single* terminating decimal which has an infinite width (i.e. is as wide as an element of Set Rnt - the set of non-terminating elements of R) has led to the belief that the *width* of Set Rnt was wider than the *width* of Set R+. This, in turn, led to the logical assumption that the *car- dinality* of Set Rnt was larger than the *cardinality* of Set R+. But this assumption was based on an invalid comparison. To use well known sets as an example, there is no *single* odd num- ber which is as wide as the width of the *set* of even numbers. The width of a single odd number is finite, by definition. The width of the set of even numbers is infinite, by the above proof. Knowing that there is no *single* odd number which is as wide as the *set* of even numbers might lead a person to assume that the cardinality of the even numbers was larger than the cardinality of the odd numbers. This is not the case. The error is that a *single* element of an infinite set is com- pared to the *end result* (i.e. meaning the totality) of another infinite set. In fact, if both sets are looked at as infinite sets, then both the odd and even numbers have the same cardinality and width. Comparing a *single* element of one infinite set to the *totality* of another infinite set is meaningless. The *end result* of both sets need to be compared to each other. In the case with 5/9ths and pi, the end result of the width of both 5/9ths and pi are countable sets of digit positions, but the *end result* of the width of the *set*, Set R5, is also infinite and countable. The end result of both processes are equal because there do not exist two different definitions for a countable set, nor should there be two different definitions. This means that there is no digit position in 5/9 or pi which is not achieved by an element of Set R+. More will be said about this below. This concludes the discussion on Theorem #1 for now. Introduction to Theorem #2: All mathematicians know that the counting numbers can be split into many mutually exclusive subsets, each of which is infinite and countable. For example, the odd and even numbers are both subsets of the counting numbers, but both sets have the same cardinality as the counting numbers. Cantor defined such a phenomenon to be very definition of an "infinite set." This simple example points out that proving things in infinite space is quite different than proving things in finite space. In infinite space, O + E = C, where all three numbers are greater than zero and equal (cardinalities) (O = Odd numbers, E = Even numbers, C = Counting numbers). In infinite space, mappings and equivalent techniques are the determiners of cardinality, not quantifiable finite numbers that can be added and subtracted. As another example, is this statement true? for all x > 0, x/1,000,000,000 < x Actually, the statement is true if x is finite, but false if x is transfinite. For example, consider this simple mapping: 1 1112223334441 2 1112223334442 3 1112223334443 4 1112223334444 5 1112223334445 6 1112223334446 ... 987 111222333444987 988 111222333444988 989 111222333444989 and so on. Note that the above mapping concatenates a string of numbers '111222333444' to the beginning of each element of the counting numbers. The set on the right represents a 'small' subset of the counting numbers (i.e. the subset of the counting numbers which have 111222333444 as their initial 12 digits), but yet it is mapped to by the counting numbers, so it is therefore infinite and countable. By using different concatenating strings, literally billions or trillions of mutually exclusive countable subsets can be extracted from a single countable set, and each set has the complete cardinality of the counting numbers! The above relation, x/1,000,000,000 < x is therefore false if x is transfinite. Theorem #2: An infinite number of mutually exclusive (i.e. pairwise disjoint) countable sets can be extracted from a single countable set, and each of these countable sets can be individually mapped to other sets. Proof: The counting numbers themselves will be used to prove this theorem. Let the 1st of these infinite sets be defined by the following series (the third column below will be discussed below): First: Set 12 1 12 2 2 1212 4 3 121212 6 4 12121212 8 5 1212121212 10 and so on. Let the 2nd of these infinite sets be defined by the following series: Second: Set 122 1 122 3 2 122122 6 3 122122122 9 4 122122122122 12 5 122122122122122 15 and so on. Let the 3rd of these infinite sets be defined by the following series: Third: Set 1222 1 1222 4 2 12221222 8 3 122212221222 12 4 1222122212221222 16 5 12221222122212221222 20 and so on. This process can go on forever, where the first element of the nth series is the number 1, followed by n 2s. The numbers in the third col- umn deals with the width of each element. These numbers demonstrate that no element of any of the above sets ever obtains an uncountable width and are therefore elements of Set A. That each of these sets can act as its own countable set for mapping purposes is established by the *left* column of each of the above series. The left column above are counting numbers being mapped to elements of the various series. These sets of counting numbers can be used as 'proxy' elements for the elements in the *middle* column for mapping pur- poses, if desired to help keep track of the mappings. In other words, *each subset* above independently qualifies as a mapping cycle to map to the real numbers or any other set. Q.E.D. The fact that any countable set can be broken down into an infinite number of mutually exclusive countable sets is a *basic characteristic* of the counting numbers. By comparison, it is a basic characteristic of the real numbers that the non-terminating numbers have an infinite and countable width. Therefore a proof designed to prove some fact about R which only used three decimal positions for each real numbers would be rejected because the proof failed to comply with the basic characteris- tics of the real numbers. Similarly, for someone to prove that R is *uncountable* by using only one cycle of a countable set in the proof violates a major basic characteristic of the counting numbers, namely, any countable set can be split up into an infinite number of mutually exclusive countable sets, each of which qualifies for a mapping cycle. The obvious argument comes up: "If a set is countable, can't it be *put back together* into one cycle of counting numbers." Whether it can or can't is irrelevant, it is an invalid way of proving theorems to sim- ply dictate restrictive rules or invalid constraints for *any* element of the proof! SECTION 2) NECESSARY ELEMENTS IN ANY PROOF THAT R IS UNCOUNTABLE This subject has already been discussed to a small degree, but this section will expand of this subject and cover more general proofs regard- ing the countability or uncountability or R. 1) Any valid proof that R is uncountable must take into account that the width of Set R+ is [N/o]. This was discussed above. This issue will be discussed in more de- tail later in this paper. 2) Any valid proof that R is uncountable must take into account the ba- sic characteristic that a single countable set can be split into an infi- nite number of mutually exclusive countable sets, each of which qualifies for its own mapping cycle. This was demonstrated above. The Diagonalization Theorem fails in this regard, it only uses one mapping cycle. This will be discussed be- low. 3) If R is uncountable, then for *each and every* terminating decimal there must exist an uncountable number of non-terminating numbers. Cantor has shown that a countable number of countable sets is count- able (this is why proving R (0,1) is countable or uncountable is equivalent to proving the same thing for all of R, because R is balanced relative to its units - meaning each unit's subset has the same cardinality). Cantor has also shown that the rational numbers are count- able, which obviously means Set R+ is countable. Since there are a countable number of terminating decimals in R, if there were only a countable number of non-terminating numbers associated with *each and ev- ery* terminating decimal, then R would be countable. Therefore, there must be at least one terminating decimal to which an uncountable number of non-terminating numbers are associated. The elements of the set R (0,1), in base 2, can be thought of as paths on an infinitely wide binary tree, as was mentioned above. A bi- nary tree is balanced by its permutation-based construction. In order for R to be uncountable, the binary tree must have an uncountable number of paths. By the nature of the binary tree, each path which terminates on the tree (i.e. branch) is *succeeded* by a binary tree equal in size to the original tree. This means that if the original tree is uncount- able, then for each terminating decimal (i.e. terminating path or branch) there must be a succeeding tree which is uncountable, because the suc- ceeding tree is equal in size to the original tree. This means that for *each and every* terminating decimal there would have to be an uncount- able number of associated non-terminating numbers. While there is a lot of redundancy in this method (i.e. every non-terminating number is counted a countable number of times, one for each branch on its path), the important thing to note is that, because the tree is balanced, there cannot be a terminating decimal which is not an initial string for only a countable number of non-terminating numbers. The Diagonalization Theorem finds one new number which symbolically represents an uncountable number of other new numbers. This particular item is properly accounted for in the Diagonalization Theorem. 4) In any proof that R is uncountable, there must be a clear delinea- tion between the rational and irrational numbers or between the terminat- ing decimals and non-terminating decimals. There are a number of proofs of the uncountability of R which make no distinction between rational and irrational numbers. In other words, a typical proof mentions the real numbers, but makes no distinction be- tween the rational and irrational numbers, which make up the real num- bers. Generally, when this happens, the proof technique can be reapplied using just the rational numbers (ignoring the irrational numbers) to prove that the rational numbers are uncountable, which would be a contra- diction and an invalidation of the proof. 5) Proofs of the uncountability of R cannot create a race between two infinite sets and declare a winner of the race. Which set is larger, the odd or even numbers? It two people were to debate that issue, going back and forth, a race between two infinite sets would ensue, and for either person to declare victory would be an error. The Diagonalization Theorem creates such a race. The race is between the width of the initial segments of the new non-terminating number as it is built, and an infinite set of terminating decimals which map to *each* initial segment of the new number as it is created, from among mapping not yet eliminated. A full discussion of this issue is beyond the scope of this short paper, but can be found in the long paper mentioned at the end of this paper. 6) Proofs of the uncountability of R cannot place an invalid constraint on any set under discussion. The Diagonalization Theorem fails this test. This will be demon- strated below. 7) Any proof of the uncountability of R cannot use circular or recur- sive logic (e.g. it cannot assume there are more non-terminating than terminating numbers). Virtually every proof that R is uncountable includes an a priori as- sumption that there are a lot more non-terminating numbers than terminat- ing numbers. But that is what the proof is supposed to prove, so assum- ing it is recursive logic. Such an assumption can invalidate the proof because it assumes the proof is true, and then uses the results of the proof to prove the theorem. The Diagonalization Theorem does not make that error. 8) No proof can *assume* that logic, symbols, formulas and even map- pings that are valid in finite space are also valid in infinite space. Any proof that R is uncountable that uses steps which seem logical in finite space may be invalid. Any time a jump is made from finite to infinite space, the theorem must *prove* that the jump is justified by using mappings or some other infinite technique. A word of warning (!): mappings which work in finite space do *not* necessarily work in infinite space! Few proofs using mappings actually prove that the mappings will work in infinite space. The counting numbers are very flexible, but fi- nite numbers are very inflexible. The Diagonalization Theorem definitely makes this error, as will be shown below, as several other theorems do also. 9) Every proof that R is countable must carefully guard against the width of the non-terminating numbers becoming uncountable. If the width of the non-terminating numbers is allowed to become un- countable in a proof, it is obvious the cardinality of the non-terminating numbers would be uncountable. But that is not permis- sible. The Diagonalization Theorem appears not to fail in this regard, but since it assumes the set of non-terminating numbers are wider than the terminating decimals, it may be considered to fail this test. SECTION 3) A SPECIFIC PROOF THAT THE DIAGONALIZATION THEOREM IS FALSE The Diagonalization Theorem starts out with an assumption. It can be worded many ways, but I prefer the following wording: Cantor's First Assumption: Given two infinite sets, Sets A and B, if it is known that Set A is countable and it can be proven there does not exist a mapping from Set A to Set B, then Set B is uncountable. I agree with this assumption. Cantor's First Assumption basically states that *if* it can be proven there does not exist a mapping from the countable set of elements to the other infinite set, then the second set is uncountable. The rationale behind the theorem is simply that there are not two "limits" or definitions of a countable set. Two sets that can be mapped to the counting numbers are equal in cardinality in all ways, by proxy if by no other way. But does the Diagonalization Theorem succeed in proving there *can- not* be a mapping from Set A to R (0,1)? That is what we will discuss. In the proof, the Diagonalization Technique assumes there exists an enu- meration from the counting numbers to R (0,1) and then proves there is an element, a "new number," which is not part of the enumeration or mapping. The conclusion is that R (0,1) is uncountable because at least one el- ement was not in the mapping and the technique is repeatable to create many other "new numbers." While logically this is correct, the *technique* which is used to prove that "there cannot be a mapping" places an invalid restriction on Set A, as will now be discussed. Also, Cantor's First Assumption, the stated assumption, is not really the assumption used in the proof. The Diagonalization Theorem does *not* use a technique consistent with Cantor's First Assumption, it uses a technique and assumption which are quite different than what is stated. In general, mapping to a countable subset of an infinite set proves nothing about the cardinality of the original set. For example, enumer- ating the odd numbers, a subset of the counting numbers, proves nothing about the cardinality of the counting numbers. The way the Diagonaliza- tion Theorem (DT) gets around such an obvious error is to basically state that: "it can be proven there does not exist a mapping." The major question about the DT is: *does* the DT prove that there does not exist a mapping from the counting numbers to R (0,1)? The an- swer is: *no*. The reason is that the DT maps to a square matrix (granted, a "square" matrix in infinite space is somewhat meaningless, but the "diagonal" in the DT implies a square matrix). In other words, the DT basically says this: "Give me a square matrix, where there are n elements and each element has a width of n (the rows of the matrix are the set elements and the columns of the matrix are the digit positions of the elements), and I will find an element that is n digits wide which is not an element of the set." This is not a proof about cardinality, it is a simple paradox. Let's analyze the DT in finite space to better understand the concepts. Consider the following set of 10 elements, each of which is 10 dig- its wide, a square matrix of digits. The right column is the "new num- ber" using the following algorithm: if the nth digit of the nth element is a 5, the nth element of the new number will be a 6, otherwise the nth element will be a 5: 1 .7867930392 .5 2 .3982176253 .55 3 .3052871672 .556 4 .5400000000 .5565 5 .6541590919 .55656 6 .8901928374 .556565 7 .2132980192 .5565655 8 .1113320992 .55656555 9 .4332113244 .556565555 10 .5432543455 .5565655556 It is easy to verify that the new number is not in the set of 10 el- ements. If one were to construct the set of all permutations of 10 dig- its taken from a pool of 10 characters, the cardinality of the set would be 100 (i.e. 10 ^ 10). It is obvious that the new number would be in the set of all representations. In finite space, the DT theorem is perfectly valid because 10 ^ n is always greater than n. The identical technique in infinite space, however, is not valid. Formulas and techniques that work in finite space do not necessarily work in infinite space. This was discussed above. There are very important pieces missing from the proof of the DT. One piece that is missing is that there is no proof that the technique that is used is valid in infinite space, and just as importantly, that the technique does prove that "there cannot be a mapping." Another piece that is missing from the proof is the *real assumption* underlying the DT: Real Assumption: *all* countable sets can be placed in a square matrix format and *no* uncountable set can be placed in a square matrix. Aside from the obvious problem of defining a "square" matrix in in- finite space, the real assumption in the DT is not Cantor's First Assump- tion, it is the assumption just mentioned. Since the technique is so im- portant to the proof, by proving that the real numbers cannot be placed into a square matrix format, the *only* possible justification for then concluding that the real numbers are uncountable is to make the assump- tion mentioned above. Suppose, for example, it could be proven that there were countable sets which could *not* be placed in a square matrix. Then the DT would conclude such a set was uncountable. Likewise, suppose it could be proven that an uncountable set could be placed in a square matrix. If so, the DT would be invalidated. The problem is that the DT does not *prove* the assumption underlying these two cases. It merely makes the assumption based on the evidence in finite space. Clearly, in finite space it is safe to assume that the number of permutations of n digits taken from a pool of 10 characters *cannot* be put into an n x n square matrix. One might then conclude that the total permutations of n digits is larger than n. In finite space this is cor- rect. In infinite space, the same assumption is made, only this time, the only thing larger than a countable set is an uncountable set, so the assumption is made that if a set cannot fit into a square matrix the set is uncountable. The DT essentially assumes that the number of permuta- tions of N/o digits taken from a pool of 10 characters has higher cardin- ality than N/o, which means it is uncountable. This is the basis for the real assumption. Also, there is no proof that the technique that is used actually proves that there *cannot* be a mapping from the counting numbers to R (0,1). There are billions and billions of ways to attempt a mapping from the counting numbers to R (0,1). Assuming there is only one way cannot be defended. The counting numbers are very flexible and can be looked at in many different ways. While this discussion is interesting, it involves the *right* side of the mapping. However, there are more significant problems on the *left* side of the mappings. There is another assumption inherent in the theorem: "the counting numbers cannot map beyond a square matrix." The left side of the assumption means that the counting numbers cannot be or- dered to extend past a single square matrix. This is untenable. The counting numbers themselves are "longer" than a square matrix (for ex- ample, the 1000000th counting number has a width of 7). Even though the counting numbers are countable and their width is countable, they do not form a square matrix. Consider the following method of breaking down Set A into subsets: Set A.1 consists of all elements of Set A which have one significant digit position (e.g. 1, 2, 3, 4, ..., 9) Set A.2 consists of all elements of Set A which have two significant digit positions (e.g. 10, 11, 12, ..., 99) Set A.3 consists of all elements of Set A which have three significant digit positions (e.g. 100, 101, 102, ..., 999) and so on. Taking only one element from each set can create a mapping to a square matrix. Consider this mapping (r_n is a real number): 5 r_1 55 r_2 555 r_3 5555 r_4 55555 r_5 and so on. This is the familiar Set A5 which has an infinite cardinality and an infinite width. It, by itself, is an increasingly minuscule subset of Set A, but by itself, it can map to a square matrix, leaving the vast ma- jority of the elements of Set A still available to map! Using the sets created in Theorem #2, the counting numbers can be so arranged that they can map to an infinite number of square matrices: 1 Set 12 2 Set 122 3 Set 1222 4 Set 12222 5 Set 122222 and so on. An infinite number of subsets of Set A can *each* map to a square matrix. The vast majority of the elements of Set A are still unused. The DT has major flaws on both sides of the mapping, but particularly on the left side. Its assumptions are also not as originally stated. Q.E.D. SECTION 4) A PROOF THAT THE REAL NUMBERS ARE COUNTABLE NOTE: It was proven above that Set R+ (0,1) would be countable even if its terminating zeros, for any width being considered (namely to any width achieved by the nonzero digits), were significant. The failure of Set R+ (0,1) to be a complete permutation is therefore irrelevant. In fact, Set A (or Set 12 for that matter), where terminating zeros are sig- nificant, could be substituted in this proof for Set R+ (0,1) with only a minor adjustment. NOTE: Obviously, proving R (0,1) is countable is equivalent to proving that all of R is countable (see above). Let us give the width set of Set R+ a name and call it Set WR+. Likewise let us call the width set of Set Rnt, Set WRnt. Sets WR+ and WRnt are two sets with nothing but counting numbers in them. We have al- ready established that the width set of Set R+ is infinite and countable; Set WR+ consists of the set {1, 2, 3, 4, ...}, namely, all counting num- bers. Since each and every element of Set Rnt has an infinite and count- able width, by definition, the width set of Set Rnt is also infinite and countable, namely {1, 2, 3, 4, ...}. We now have two infinite sets of counting numbers. It is important to remember that Sets WR+ and WRnt contain *nothing* but counting numbers and it is important to remember that Set WR+ has been proven to be infinite and countable. There are two cases to consider: Case #1: There exists a mapping from Set WR+ to Set WRnt. Step 1: By assumption, this case means that given any element of Set WRnt, there exists an element of Set WR+, and that there is an element of a countable mapping between these two elements. Step 2: Since Sets WRnt and WR+ map to digit positions in Sets Rnt and R+, respectively, Step 1 means that given any digit position in Set Rnt, there exists a digit position in Set R+. Step 3: It was shown above that for any digit position, n, achieved by Set R+, the cardinality of Set R+, as if n were the final digit position achieved by Set R+ (which it is *not*), consists of all permutations of n digits from a pool of 10 characters. Step 4: It is obvious that for any digit position, n, achieved by Set Rnt, the cardinality of Set Rnt, as if n were the final digit position achieved by Set Rnt (which it is *not*), cannot exceed the number of per- mutations of n digits from a pool of 10 characters. Step 5: Keeping Steps 4 and 5 in mind, because given any digit position in Set Rnt, there exists an equal digit position in Set R+, the cardinal- ity (i.e. number of representations) of Set Rnt cannot exceed the cardin- ality of Set R+ for any digit position, n. Step 6: Therefore, *by assumption*, there does not exist a digit posi- tion, n, in Set Rnt for which the cardinality of Set Rnt exceeds the car- dinality of Set R+. Step 7: Set Rnt can never achieve a digit position for which the cardin- ality of Set Rnt exceeds the cardinality of Set R+. Step 8: The cardinality of Set Rnt can never exceed the cardinality of Set R+, because there is no digit position in Set Rnt not available to Set R+. Step 9: By assumption, the width sets of Sets R+ and Rnt are permanently linked together by a mapping. As such, the width of neither set can es- cape the bond resulting from this mapping. Step 10: Because of their similar permutation construction, neither set can excel in cardinality unless that set can escape the linkage or bond- ing of widths. Step 11: By assumption, neither set can escape the linkage of widths and neither set can excel in cardinality. Step 12: Because Set R+ never becomes uncountable, Set Rnt can never be- come uncountable (!) because, by assumption, its width can never exceed the width of Set R+. Set R+ is countable, and Set R+ has the same permutation construction as does Set Rnt. Step 13: Set Rnt is therefore countable, because it can never become un- countable. Step 14: Because an infinite number of countable sets is countable, two countable sets (Sets R+ and Rnt) are also countable. Step 15: R is countable in Case #1. Case #2: There does *not* exist a mapping from Set WR+ to Set WRnt. Step 1: By assumption, since it is known that Set WR+ is infinite and countable, there exists an element of Set WRnt which is not an element of Set WR+. Step 2: Because Set WR+ is known to be countable, and because by assump- tion there is no mapping from Set WR+ to Set WRnt, then by Cantor's First Assumption, Set WRnt is uncountable. Step 3: Because Set WRnt is uncountable, the number of digit positions in Set Rnt is uncountable, by construction. Step 4: This is a contradiction because the number of digit positions in each and every non-terminating number is countable, therefore by con- struction and definition, the width of Set Rnt, Set WRnt, cannot be un- countable. Step 5: Case #2 is rejected. Q.E.D. While the above proof might be surprising, consider the following three sets, and determine which of the three sets is geometrically longer: Set 1: The real number line from 0 to infinity (this is an infinite set). (Think of this set as the width of the non-terminating decimals) Set 2: The summation of lengths of the unit intervals in R: [0,1] plus [1,2] plus [2,3] plus [3,4], etc. (Think of this set as the width of the terminating decimals) Set 3: The ultimate length achieved by these intervals in R: [0,1] then [0,2] then [0,3] then [0,4] then [0,5], etc. (Think of this set also as the width of the terminating decimals) It is clear that these three sets are equal in length. Infinite sets of finite intervals are equal in every way to infinite sets. Likewise, because there is a direct link between the widths of Sets R+ and Rnt and the number of representations in each set (the link is the permutation construction), if the widths of Sets R+ and Rnt are equal, the number of their representations is equal, meaning their cardinality is equal. A comment could be made that Set Rnt achieves infinite width simul- taneously, but Set R+ must achieve it digit by digit. But if Set Rnt achieves an infinite width simultaneously, why doesn't Set R+ achieve it simultaneously also? It is a double standard to say that one infinite set is larger than another or to place a physical restriction on one in- finite set to make it appear larger than another infinite set. Remember, the DT creates the new number - a *non-terminating* number - digit by digit, after an examination of a mapping, so how did the new number achieve infinite width simultaneously? Fair is fair. SECTION 5) CONCLUDING COMMENTS I would greatly appreciate your comments on this paper. To send your comments, simply E-Mail me at: webster@tyrell.net, or if that does not work, I can be reached at: Webster Kehr; P.O. Box 7452; Overland Park, KS 66207. This short paper is basically a synopsis of an 80 page paper I re- leased on December 27, 1993, which in turn was the forth draft of a paper originally released on July 1, 1993. While this paper has one proof that R is countable, the December 27th paper has 12 proofs. The proof in this paper is the 5th of the 12 proofs. The full paper also deals with such issues as: omega, the Power Set of a countable set (e.g. there is a map- ping from a countable set to the set of all of its subsets), other proofs that the Diagonalization Theorem is false, a counterexample to Cantor's 1973/74 proof that R is uncountable, and many other topics. Copies of this paper are free and are available at the above address. Thank you in advance for your comments.